#include <common.h>

class MergeSort {
public:
    vector<int> sort(const std::vector<int>& nums) {
        auto res = merge_sort(nums, 0, nums.size() - 1);
        return res;
    }

private:
    vector<int> merge_sort(std::vector<int> nums, int left, int right) {
        if (left == right) {
            return {nums[left]};
        }
        int mid = (left + right) / 2;
        auto left_array = merge_sort(nums, left, mid);
        auto right_array = merge_sort(nums, mid + 1, right);

        vector<int> result;
        int m = 0, n = 0, m_len = left_array.size() - 1, n_len = right_array.size() - 1;
        while (m <= m_len && n <= n_len) {
            if (left_array[m] <= right_array[n]) {
                result.push_back(left_array[m++]);
            } else {
                result.push_back(right_array[n++]);
            }
        }
        while (m <= m_len) {
            result.push_back(left_array[m++]);
        }
        while (n <= n_len) {
            result.push_back(right_array[n++]);
        }
        return result;
    }
};

int main(int argc, char *argv[]) {
    MergeSort ms;
    auto generate_random_vector = Random::generate_random_vector(50,1000);
    cout<<printer::int_array_to_string(generate_random_vector)<<endl;
    auto res = ms.sort(generate_random_vector);
    cout<<printer::int_array_to_string(res)<<endl;
    return 0;
}
